<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Kreisgraph</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Kreisgraph"> <link href="./_mw_/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Kreisgraph rootpage-Kreisgraph skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Kreisgraph</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p>Ein <b>Kreisgraph</b>, kurz <b>Kreis</b>, ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a> mit einfacher Struktur. Ein Kreisgraph besitzt immer gleich viele <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> und <a href="Kante_(Graphentheorie)" title="Kante (Graphentheorie)">Kanten</a>, wobei alle Knoten im <a href="Kreis_(Graphentheorie)" class="mw-redirect" title="Kreis (Graphentheorie)">Kreis</a> miteinander verbunden sind. Kreisgraphen mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten werden mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"></span> bezeichnet. Eine <a href="Topologie_(Rechnernetz)" title="Topologie (Rechnernetz)">Netzwerktopologie</a> in Form eines Kreisgraphen wird <a href="Ring-Topologie" class="mw-redirect" title="Ring-Topologie">Ring-Topologie</a> genannt.
</p>
<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>
<p>Ein Kreisgraph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"></span> ist ein <a href="Ungerichteter_Graph" class="mw-redirect" title="Ungerichteter Graph">ungerichteter Graph</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (V,E)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>V</mi>
<mo>,</mo>
<mi>E</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (V,E)}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a01724c7d662052bd5f1c34cb725c8001634069a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.406ex; height:2.843ex;" alt="{\displaystyle (V,E)}" loading="lazy"></span> bestehend aus den <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V=\{v_{1},\ldots ,v_{n}\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle V=\{v_{1},\ldots ,v_{n}\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c4f122df9a6f586948502b915bf830750fef59a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.917ex; height:2.843ex;" alt="{\displaystyle V=\{v_{1},\ldots ,v_{n}\}}" loading="lazy"></span></dd></dl>
<p>und den <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Kanten
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E=\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\ldots ,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>E</mi>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mo fence="false" stretchy="false">{</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo fence="false" stretchy="false">}</mo>
<mo>,</mo>
<mo fence="false" stretchy="false">{</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
<mo fence="false" stretchy="false">}</mo>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mo fence="false" stretchy="false">{</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo fence="false" stretchy="false">}</mo>
<mo>,</mo>
<mo fence="false" stretchy="false">{</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>v</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo fence="false" stretchy="false">}</mo>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle E=\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\ldots ,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/18ac5077ecf2eb5446757b15c26938fb58d70807.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.929ex; height:2.843ex;" alt="{\displaystyle E=\{\{v_{1},v_{2}\},\{v_{2},v_{3}\},\ldots ,\{v_{n-1},v_{n}\},\{v_{n},v_{1}\}\}}" loading="lazy"></span>,</dd></dl>
<p>wobei meist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 3}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>≥<!-- ≥ --></mo>
<mn>3</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n\geq 3}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73136e4a27fe39c123d16a7808e76d3162ce42bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 3}" loading="lazy"></span> angenommen wird. Ein Kreisgraph mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten wird auch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-Kreis oder <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-Zyklus genannt.
</p>
<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>
<p>Im Folgenden werden nur Kreisgraphen bestehend aus mindestens drei Knoten betrachtet.
</p>
<ul><li>Alle Kreisgraphen sind <a href="Zusammenh%C3%A4ngender_Graph" class="mw-redirect" title="Zusammenhängender Graph">zusammenhängend</a>, <a href="Planarer_Graph" title="Planarer Graph">planar</a>, <a href="Zyklus_(Graphentheorie)" title="Zyklus (Graphentheorie)">zyklisch</a>, <a href="Eulerscher_Graph" class="mw-redirect" title="Eulerscher Graph">eulersch</a> und <a href="Hamiltonscher_Graph" class="mw-redirect" title="Hamiltonscher Graph">hamiltonsch</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li>
<li>Alle Kreisgraphen sind <a href="Regul%C3%A4rer_Graph" title="Regulärer Graph">2-regulär</a>, das heißt jeder Knoten hat den <a href="Grad_(Graphentheorie)" title="Grad (Graphentheorie)">Grad</a> zwei.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li>
<li>Alle Kreisgraphen haben die <a href="Baumweite" title="Baumweite">Baumweite</a> zwei.</li>
<li>Der <a href="Kantengraph" title="Kantengraph">Kantengraph</a> des Kreisgraphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"></span> ist <a href="Isomorphie_von_Graphen" title="Isomorphie von Graphen">isomorph</a> zu seinem Ausgangsgraph, also wieder ein Kreisgraph mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li>
<li>Der <a href="Durchmesser_(Graphentheorie)" class="mw-redirect" title="Durchmesser (Graphentheorie)">Durchmesser</a> und die <a href="Stabilit%C3%A4tszahl" class="mw-redirect" title="Stabilitätszahl">Stabilitätszahl</a> des Kreisgraphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"></span> beträgt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">⌊<!-- ⌊ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="false" scriptlevel="0">
<mfrac>
<mi>n</mi>
<mn>2</mn>
</mfrac>
</mstyle>
</mrow>
<mo fence="false" stretchy="false">⌋<!-- ⌋ --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e93e66f6a982a4a7a3abba31a16e0eaa358a7e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.887ex; height:3.176ex;" alt="{\displaystyle \lfloor {\tfrac {n}{2}}\rfloor }" loading="lazy"></span>.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li>
<li>Die <a href="Chromatische_Zahl" title="Chromatische Zahl">chromatische Zahl</a> des Kreisgraphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"></span> ist zwei, wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> gerade ist und drei, wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> ungerade ist.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>
<li>Das <a href="Chromatisches_Polynom" title="Chromatisches Polynom">chromatische Polynom</a> des Kreisgraphen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"></span> ist <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (-1)^{n}(\lambda -1)+(\lambda -1)^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
<mo stretchy="false">(</mo>
<mi>λ<!-- λ --></mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mo stretchy="false">(</mo>
<mi>λ<!-- λ --></mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (-1)^{n}(\lambda -1)+(\lambda -1)^{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb5ecc1ddb343156628f372a5244f9ed182cf083.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.392ex; height:2.843ex;" alt="{\displaystyle (-1)^{n}(\lambda -1)+(\lambda -1)^{n}}" loading="lazy"></span>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></li>
<li>Alle Kreisgraphen sind für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq 2}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>≥<!-- ≥ --></mo>
<mn>2</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n\geq 2}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e6bf67f9d06ca3af619657f8d20ee1322da77174.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.656ex; height:2.343ex;" alt="{\displaystyle n\geq 2}" loading="lazy"></span> zueinander <a href="Hom%C3%B6omorphie_(Graphentheorie)" class="mw-redirect" title="Homöomorphie (Graphentheorie)">homöomorph</a>.</li></ul>
<p>Eigenschaften spezieller Kreisgraphen sind:
</p>
<ul><li>Der Kreisgraph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{3}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>3</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{3}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/66e9abeb5057b7afbf88e3169101849354f13c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.716ex; height:2.509ex;" alt="{\displaystyle C_{3}}" loading="lazy"></span> ist ein spezieller <a href="Dreiecksgraph" title="Dreiecksgraph">Dreiecksgraph</a>.</li>
<li>Der Kreisgraph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{4}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>4</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{4}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/59cf1a8e46030a81fc175be95561e4f161241a70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.716ex; height:2.509ex;" alt="{\displaystyle C_{4}}" loading="lazy"></span> ist ein spezieller <a href="Gittergraph" title="Gittergraph">Gittergraph</a>.</li>
<li>Der Kreisgraph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{5}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>5</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{5}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6d93b495ef896a93e1183aa55f53d32daa538738.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.716ex; height:2.509ex;" alt="{\displaystyle C_{5}}" loading="lazy"></span> ist der bis auf Isomorphie eindeutige <a href="Komplementgraph" title="Komplementgraph">selbstkomplementäre</a> Graph mit 5 Knoten.</li>
<li>Der Kreisgraph <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{6}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>C</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>6</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle C_{6}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17692472a5b1f5de8b8b27603154198c16b61fbc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.716ex; height:2.509ex;" alt="{\displaystyle C_{6}}" loading="lazy"></span> ist der kleinste <a href="Regul%C3%A4rer_Graph" title="Regulärer Graph">reguläre Graph</a>, der nicht stark regulär ist.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>
<ul><li><a href="Linearer_Graph" title="Linearer Graph">Linearer Graph</a></li>
<li><a href="Sterngraph" title="Sterngraph">Sterngraph</a></li>
<li><a href="Leitergraph" title="Leitergraph">Leitergraph</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li>Peter Tittmann: <cite style="font-style:italic">Graphentheorie: Eine anwendungsorientierte Einführung</cite>. Hanser Verlag, 2003, ISBN 3-446-22343-6.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Peter+Tittmann&rft.btitle=Graphentheorie%3A+Eine+anwendungsorientierte+Einf%C3%BChrung&rft.date=2003&rft.genre=book&rft.isbn=3446223436&rft.pub=Hanser+Verlag" style="display:none"> </span></li>
<li>C. Vasudev: <cite style="font-style:italic">Graph theory with applications</cite>. New Age International, 2006, ISBN 81-224-1737-X.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=C.+Vasudev&rft.btitle=Graph+theory+with+applications&rft.date=2006&rft.genre=book&rft.isbn=812241737X&rft.pub=New+Age+International" style="display:none"> </span></li>
<li>Walter D. Wallis: <cite style="font-style:italic">A Beginner's Guide to Graph Theory</cite>. 2. Auflage. Springer, 2007, ISBN 0-8176-4484-9.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Walter+D.+Wallis&rft.btitle=A+Beginner%27s+Guide+to+Graph+Theory&rft.date=2007&rft.edition=2.&rft.genre=book&rft.isbn=0817644849&rft.pub=Springer" style="display:none"> </span></li></ul>
<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>
<ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Vasudev: <cite style="font-style:italic">Graph theory with applications</cite>. 2006, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>76</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Vasudev&rft.btitle=Graph+theory+with+applications&rft.date=2006&rft.genre=book&rft.pages=76" style="display:none"> </span></span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Vasudev: <cite style="font-style:italic">Graph theory with applications</cite>. 2006, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>50</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Vasudev&rft.btitle=Graph+theory+with+applications&rft.date=2006&rft.genre=book&rft.pages=50" style="display:none"> </span></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Vasudev: <cite style="font-style:italic">Graph theory with applications</cite>. 2006, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>458</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Vasudev&rft.btitle=Graph+theory+with+applications&rft.date=2006&rft.genre=book&rft.pages=458" style="display:none"> </span></span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">Tittmann: <cite style="font-style:italic">Graphentheorie: Eine anwendungsorientierte Einführung</cite>. 2003, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>35,60</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Tittmann&rft.btitle=Graphentheorie%3A+Eine+anwendungsorientierte+Einf%C3%BChrung&rft.date=2003&rft.genre=book&rft.pages=35%2C60" style="display:none"> </span></span>
</li>
<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Wallis: <cite style="font-style:italic">A Beginner's Guide to Graph Theory</cite>. 2007, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>94</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Wallis&rft.btitle=A+Beginner%27s+Guide+to+Graph+Theory&rft.date=2007&rft.genre=book&rft.pages=94" style="display:none"> </span></span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text">Robert A. Wilson: <cite style="font-style:italic">Graphs, Colourings and the Four-Colour Theorem</cite>. Oxford University Press, 2002, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>101</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Kreisgraph&rft.au=Robert+A.+Wilson&rft.btitle=Graphs%2C+Colourings+and+the+Four-Colour+Theorem&rft.date=2002&rft.genre=book&rft.pages=101&rft.pub=Oxford+University+Press" style="display:none"> </span></span>
</li>
</ol>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<ul><li><a href="Eric_Weisstein" title="Eric Weisstein">Eric W. Weisstein</a>: <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/CycleGraph.html"><i>Cycle Graph</i>.</a> In: <i><a href="MathWorld" title="MathWorld">MathWorld</a></i> (englisch).</li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-11-13" href="https://de.wikipedia.org/wiki/?title=Kreisgraph&oldid=250314318">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>